/* -*-c++-*- */
/* osgEarth - Dynamic map generation toolkit for OpenSceneGraph
* Copyright 2015 Pelican Mapping
* http://osgearth.org
*
* osgEarth is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
* IN THE SOFTWARE.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this program.  If not, see <http://www.gnu.org/licenses/>
*/
#ifndef _CONTAINERS_H
#define _CONTAINERS_H 1

#include "kernel/threading/mutex.h"
#include "kernel/ref_ptr.h"
#include "kernel/observer_ptr.h"
#include "kernel/threading/mutex.h"
#include "kernel/threading/thread.h"
#include <list>
#include <vector>
#include <set>
#include <map>

namespace FD
{
	namespace Kernel
	{
		/**
		* A std::map-like map that uses a vector and a getUID method for keying.
		* DATA must have a getUID() method.
		*/
		template<typename KEY,typename DATA>
		struct vector_map
		{
			struct ENTRY {
				inline const KEY&  key()  const { return _key; }
				inline const DATA& data() const { return _data; }
				inline DATA&       data()       { return _data; }
				KEY   _key;
				DATA _data;
			};
			typedef std::vector<ENTRY> container_t;

			//typedef std::vector<KEY>  keys_t;
			//typedef std::vector<DATA> container_t;

			typedef typename container_t::iterator       iterator;
			typedef typename container_t::const_iterator const_iterator;

			container_t _container;        

			inline DATA& operator[](const KEY& key) {
				for(unsigned i=0; i<_container.size(); ++i) {
					if (_container[i]._key == key) {
						return _container[i]._data;
					}
				}
				_container.resize(_container.size()+1);
				//_container.push_back(ENTRY());
				_container.back()._key = key;
				return _container.back()._data;
			}

			inline DATA* find(const KEY& key) {
				for(unsigned i=0; i<_container.size(); ++i) {
					if (_container[i]._key == key) {
						return &_container[i]._data;
					}
				}
				return 0L;
			}

			inline const DATA* find(const KEY& key) const {
				for(unsigned i=0; i<_container.size(); ++i) {
					if (_container[i]._key == key) {
						return &_container[i]._data;
					}
				}
				return 0L;
			}

			inline const_iterator begin() const { return _container.begin(); }
			inline const_iterator end()   const { return _container.end(); }
			inline iterator begin()             { return _container.begin(); }
			inline iterator end()               { return _container.end(); }

			inline bool empty() const { return _container.empty(); }

			inline void clear() { _container.clear(); }

			//iterator erase(iterator& i) {
			//    iterator j = i; ++j;
			//    *i = _data.at(_data.size()-1);
			//    _data.resize(_data.size()-1);
			//    return j;
			//}

			inline void erase(const KEY& key) {
				for(unsigned i=0; i<_container.size(); ++i) {
					if (_container[i]._key == key) {
						if (i+1 < _container.size()) {
							_container[i] = _container[_container.size()-1];
						}
						_container.resize(_container.size()-1);
						break;
					}
				}
			}

			inline int size() const { return _container.size(); }

			template<typename InputIterator>
			void insert(InputIterator a, InputIterator b) {
				for(InputIterator i = a; i != b; ++i) (*this)[i->first] = i->second;
			}
		};

		/**
		* A std::map-like container that is faster than std::map for small amounts
		* of data accessed by a single user
		*/
		template<typename KEY, typename DATA>
		struct fast_map
		{
			typedef std::pair<KEY,DATA> entry_t;
			typedef std::list<entry_t>  list_t;

			typedef typename list_t::iterator       iterator;
			typedef typename list_t::const_iterator const_iterator;

			list_t _data;
			KEY    _lastKey;

			DATA& operator[] (const KEY& key) {
				for( iterator i = _data.begin(); i != _data.end(); ++i ) {
					if ( i->first == key ) {
						if ( _lastKey == key && i != _data.begin() ) {
							_data.insert(begin(), *i);
							_data.erase(i);
							return _data.front().second;
						}
						else {
							_lastKey = key;
							return i->second;
						}
					}
				}
				_data.push_back(entry_t(key,DATA()));
				return _data.back().second;
			}

			iterator find( const KEY& key ) {
				for( iterator i = _data.begin(); i != _data.end(); ++i ) {
					if ( i->first == key ) {
						return i;
					}
				}
				return end();
			}

			const_iterator find( const KEY& key ) const {
				for( const_iterator i = _data.begin(); i != _data.end(); ++i ) {
					if ( i->first == key ) {
						return i;
					}
				}
				return end();
			}

			const_iterator begin() const { return _data.begin(); }
			const_iterator end() const { return _data.end(); }
			iterator begin() { return _data.begin(); }
			iterator end() { return _data.end(); }

			bool empty() const { return _data.empty(); }

			void clear() { _data.clear(); }

			iterator erase(iterator& i) { return _data.erase( i ); }

			void erase(const KEY& key) {
				iterator i = find(key);
				if ( i != end() ) {
					erase( i );
				}
			}

			int size() const { return _data.size(); }

			template<typename InputIterator>
			void insert(InputIterator a, InputIterator b) {
				for(InputIterator i = a; i != b; ++i) (*this)[i->first] = i->second;
			}
		};

		//------------------------------------------------------------------------

		struct CacheStats
		{
		public:
			CacheStats( unsigned entries, unsigned maxEntries, unsigned queries, float hitRatio )
				: _entries(entries), _maxEntries(maxEntries), _queries(queries), _hitRatio(hitRatio) { }

			/** dtor */
			virtual ~CacheStats() { }

			unsigned _entries;
			unsigned _maxEntries;
			unsigned _queries;
			float    _hitRatio;
		};

		//------------------------------------------------------------------------

		/**
		* Least-recently-used cache class.
		* K = key type, T = value type
		*
		* usage:
		*    LRUCache<K,T> cache;
		*    cache.put( key, value );
		*    LRUCache.Record rec = cache.get( key );
		*    if ( rec.valid() )
		*        const T& value = rec.value();
		*/
		template<typename K, typename T, typename COMPARE=std::less<K> >
		class LRUCache
		{
		public:
			struct Record {
				Record() : _valid(false) { }
				Record(const T& value) : _value(value), _valid(true) { }
				bool valid() const { return _valid; }
				const T& value() const { return _value; }
			private:
				bool _valid;
				T    _value;
				friend class LRUCache;
			};

		protected:
			typedef typename std::list<K>::iterator      lru_iter;
			typedef typename std::list<K>                lru_type;
			typedef typename std::pair<T, lru_iter>      map_value_type;
			typedef typename std::map<K, map_value_type> map_type;
			typedef typename map_type::iterator          map_iter;

			map_type _map;
			lru_type _lru;
			unsigned _maxcontainers;
			unsigned _buf;
			unsigned _queries;
			unsigned _hits;
			bool     _threadsafe;
			mutable FD::Kernel::Mutex _mutex;

		public:
			LRUCache( unsigned max =100 ) : _maxcontainers(max), _threadsafe(false) {
				_buf = _maxcontainers/10;
				_queries = 0;
				_hits = 0;
			}
			LRUCache( bool threadsafe, unsigned max =100 ) : _maxcontainers(max), _threadsafe(threadsafe) {
				_buf = _maxcontainers/10;
				_queries = 0;
				_hits = 0;
			}

			/** dtor */
			virtual ~LRUCache() { }

			void insert( const K& key, const T& value ) {
				if ( _threadsafe ) {
					FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
					insert_impl( key, value );
				}
				else {
					insert_impl( key, value );
				}
			}

			bool get( const K& key, Record& out ) {
				if ( _threadsafe ) {
					FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
					get_impl( key, out );
				}
				else {
					get_impl( key, out );
				}
				return out.valid();
			}

			bool has( const K& key ) {
				if ( _threadsafe ) {
					FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
					return has_impl( key );
				}
				else {
					return has_impl( key );
				}
			}

			void erase( const K& key ) {
				if ( _threadsafe ) {
					FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
					erase_impl( key );
				}
				else {
					erase_impl( key );
				}
			}

			void clear() {
				if ( _threadsafe ) {
					FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
					clear_impl();
				}
				else {
					clear_impl();
				}
			}

			void setMaxSize( unsigned max ) {
				if ( _threadsafe ) {
					FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
					setMaxSize_impl( max );
				}
				else {
					setMaxSize_impl( max );
				}
			}

			unsigned getMaxSize() const {
				return _maxcontainers;
			}

			CacheStats getStats() const {
				return CacheStats(
					_lru.size(), _maxcontainers, _queries, _queries > 0 ? (float)_hits/(float)_queries : 0.0f );
			}

		private:

			void insert_impl( const K& key, const T& value ) {
				map_iter mi = _map.find( key );
				if ( mi != _map.end() ) {
					_lru.erase( mi->second.second );
					mi->second.first = value;
					_lru.push_back( key );
					mi->second.second = _lru.end();
					mi->second.second--;
				}
				else {
					_lru.push_back( key );
					lru_iter last = _lru.end(); last--;
					_map[key] = std::make_pair(value, last);
				}

				if ( _lru.size() > _maxcontainers ) {
					for( unsigned i=0; i < _buf; ++i ) {
						const K& key = _lru.front();
						_map.erase( key );
						_lru.pop_front();
					}
				}
			}

			void get_impl( const K& key, Record& result ) {
				_queries++;
				map_iter mi = _map.find( key );
				if ( mi != _map.end() ) {
					_lru.erase( mi->second.second );
					_lru.push_back( key );
					lru_iter new_iter = _lru.end(); new_iter--;
					mi->second.second = new_iter;
					_hits++;
					result._value = mi->second.first;
					result._valid = true;
					//return Record( &(mi->second.first) );
				}
				//else {
				//    return Record( 0L );
				//}
			}

			bool has_impl( const K& key ) {
				return _map.find( key ) != _map.end();
			}

			void erase_impl( const K& key ) {
				map_iter mi = _map.find( key );
				if ( mi != _map.end() ) {
					_lru.erase( mi->second.second );
					_map.erase( mi );
				}
			}

			void clear_impl() {
				_lru.clear();
				_map.clear();
				_queries = 0;
				_hits = 0;
			}

			void setMaxSize_impl( unsigned max ) {
				_maxcontainers = max;
				_buf = max/10;
				while( _lru.size() > _maxcontainers ) {
					const K& key = _lru.front();
					_map.erase( key );
					_lru.pop_front();
				}
			}

		};

		//--------------------------------------------------------------------

		/**
		* Same of osg::MixinVector, but with a superclass template parameter.
		*/
		template<class ValueT/*, class SuperClass*/>
		class MixinVector// : public SuperClass
		{
			typedef typename std::vector<ValueT> vector_type;
		public:
			typedef typename vector_type::allocator_type allocator_type;
			typedef typename vector_type::value_type value_type;
			typedef typename vector_type::const_pointer const_pointer;
			typedef typename vector_type::pointer pointer;
			typedef typename vector_type::const_reference const_reference;
			typedef typename vector_type::reference reference;
			typedef typename vector_type::const_iterator const_iterator;
			typedef typename vector_type::iterator iterator;
			typedef typename vector_type::const_reverse_iterator const_reverse_iterator;
			typedef typename vector_type::reverse_iterator reverse_iterator;
			typedef typename vector_type::size_type size_type;
			typedef typename vector_type::difference_type difference_type;

			explicit MixinVector() : _impl()
			{
			}

			explicit MixinVector(size_type initial_size, const value_type& fill_value = value_type())
				: _impl(initial_size, fill_value)
			{
			}

			template<class InputIterator>
			MixinVector(InputIterator first, InputIterator last)
				: _impl(first, last)
			{
			}

			MixinVector(const vector_type& other)
				: _impl(other)
			{
			}

			MixinVector(const MixinVector& other)
				: _impl(other._impl)
			{
			}

			MixinVector& operator=(const vector_type& other)
			{
				_impl = other;
				return *this;
			}

			MixinVector& operator=(const MixinVector& other)
			{
				_impl = other._impl;
				return *this;
			}

			virtual ~MixinVector() {}

			void clear() { _impl.clear(); }
			void resize(size_type new_size, const value_type& fill_value = value_type()) { _impl.resize(new_size, fill_value); }
			void reserve(size_type new_capacity) { _impl.reserve(new_capacity); }

			void swap(vector_type& other) { _impl.swap(other); }
			void swap(MixinVector& other) { _impl.swap(other._impl); }

			bool empty() const { return _impl.empty(); }
			size_type size() const { return _impl.size(); }
			size_type capacity() const { return _impl.capacity(); }
			size_type max_size() const { return _impl.max_size(); }
			allocator_type get_allocator() const { return _impl.get_allocator(); }

			const_iterator begin() const { return _impl.begin(); }
			iterator begin() { return _impl.begin(); }
			const_iterator end() const { return _impl.end(); }
			iterator end() { return _impl.end(); }

			const_reverse_iterator rbegin() const { return _impl.rbegin(); }
			reverse_iterator rbegin() { return _impl.rbegin(); }
			const_reverse_iterator rend() const { return _impl.rend(); }
			reverse_iterator rend() { return _impl.rend(); }

			const_reference operator[](size_type index) const { return _impl[index]; }
			reference operator[](size_type index) { return _impl[index]; }

			const_reference at(size_type index) const { return _impl.at(index); }
			reference at(size_type index) { return _impl.at(index); }

			void assign(size_type count, const value_type& value) { _impl.assign(count, value); }
			template<class Iter>
			void assign(Iter first, Iter last) { _impl.assign(first, last); }

			void push_back(const value_type& value) { _impl.push_back(value); }
			void pop_back() { _impl.pop_back(); }

			iterator erase(iterator where) { return _impl.erase(where); }
			iterator erase(iterator first, iterator last) { return _impl.erase(first, last); }

			iterator insert(iterator where, const value_type& value) { return _impl.insert(where, value); }

			template<class InputIterator>
			void insert(iterator where, InputIterator first, InputIterator last)
			{
				_impl.insert(where, first, last);
			}

			void insert(iterator where, size_type count, const value_type& value)
			{
				_impl.insert(where, count, value);
			}

			const_reference back() const { return _impl.back(); }
			reference back() { return _impl.back(); }
			const_reference front() const { return _impl.front(); }
			reference front() { return _impl.front(); }

			vector_type& asVector() { return _impl; }
			const vector_type& asVector() const { return _impl; }

			friend inline bool operator==(const MixinVector<ValueT/*,SuperClass*/>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left._impl == right._impl; }
			friend inline bool operator==(const MixinVector<ValueT/*,SuperClass*/>& left, const std::vector<ValueT>& right) { return left._impl == right; }
			friend inline bool operator==(const std::vector<ValueT>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left == right._impl; }

			friend inline bool operator!=(const MixinVector<ValueT/*,SuperClass*/>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left._impl != right._impl; }
			friend inline bool operator!=(const MixinVector<ValueT/*,SuperClass*/>& left, const std::vector<ValueT>& right) { return left._impl != right; }
			friend inline bool operator!=(const std::vector<ValueT>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left != right._impl; }

			friend inline bool operator<(const MixinVector<ValueT/*,SuperClass*/>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left._impl < right._impl; }
			friend inline bool operator<(const MixinVector<ValueT/*,SuperClass*/>& left, const std::vector<ValueT>& right) { return left._impl < right; }
			friend inline bool operator<(const std::vector<ValueT>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left < right._impl; }

			friend inline bool operator>(const MixinVector<ValueT/*,SuperClass*/>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left._impl > right._impl; }
			friend inline bool operator>(const MixinVector<ValueT/*,SuperClass*/>& left, const std::vector<ValueT>& right) { return left._impl > right; }
			friend inline bool operator>(const std::vector<ValueT>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left > right._impl; }

			friend inline bool operator<=(const MixinVector<ValueT/*,SuperClass*/>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left._impl <= right._impl; }
			friend inline bool operator<=(const MixinVector<ValueT/*,SuperClass*/>& left, const std::vector<ValueT>& right) { return left._impl <= right; }
			friend inline bool operator<=(const std::vector<ValueT>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left <= right._impl; }

			friend inline bool operator>=(const MixinVector<ValueT/*,SuperClass*/>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left._impl >= right._impl; }
			friend inline bool operator>=(const MixinVector<ValueT/*,SuperClass*/>& left, const std::vector<ValueT>& right) { return left._impl >= right; }
			friend inline bool operator>=(const std::vector<ValueT>& left, const MixinVector<ValueT/*,SuperClass*/>& right) { return left >= right._impl; }

		private:
			vector_type _impl;
		};


		///** Template for per-thread data storage */
		//template<typename T>
		//struct PerThread
		//{
		//	T& get() {
		//		FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
		//		return _data[FD::Kernel::Thread::getThreadID()];
		//	}
		//private:
		//	std::map<unsigned,T> _data;
		//	FD::Kernel::Mutex     _mutex;
		//};


		/** Template for thread safe per-object data storage */
		template<typename KEY, typename DATA>
		struct PerObjectMap
		{
			DATA& get(KEY k)
			{
				{
					FD::Kernel::ScopedLock readLock(_mutex);
					typename std::map<KEY,DATA>::iterator i = _data.find(k);
					if ( i != _data.end() )
						return i->second;
				}
				{
					FD::Kernel::ScopedLock lock(_mutex);
					typename std::map<KEY,DATA>::iterator i = _data.find(k);
					if ( i != _data.end() )
						return i->second;
					else
						return _data[k];
				}
			}

			void remove(KEY k)
			{
				FD::Kernel::ScopedLock exclusive(_mutex);
				_data.erase( k );
			}

		private:
			std::map<KEY,DATA>                  _data;
			FD::Kernel::Mutex _mutex;

		};

		/** Template for thread safe per-object data storage */
		template<typename KEY, typename DATA>
		struct PerObjectFastMap
		{
			DATA& get(KEY k)
			{
				{
					FD::Kernel::ScopedLock readLock(_mutex);
					typename osgEarth::fast_map<KEY,DATA>::iterator i = _data.find(k);
					if ( i != _data.end() )
						return i->second;
				}
				{
					FD::Kernel::ScopedLock lock(_mutex);
					typename osgEarth::fast_map<KEY,DATA>::iterator i = _data.find(k);
					if ( i != _data.end() )
						return i->second;
					else
						return _data[k];
				}
			}

			void remove(KEY k)
			{
				FD::Kernel::ScopedLock exclusive(_mutex);
				_data.erase( k );
			}

		private:
			fast_map<KEY,DATA>        _data;
			FD::Kernel::Mutex _mutex;
		};

		/** Template for thread safe per-object data storage */
		template<typename KEY, typename DATA>
		struct PerObjectRefMap
		{
			DATA* get(KEY k)
			{
				FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
				typename std::map<KEY,FD::Kernel::ref_ptr<DATA > >::const_iterator i = _data.find(k);
				if ( i != _data.end() )
					return i->second.get();

				return 0L;
			}

			DATA* getOrCreate(KEY k, DATA* newDataIfNeeded)
			{
				FD::Kernel::ref_ptr<DATA> _refReleaser = newDataIfNeeded;
				{
					FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
					typename std::map<KEY,FD::Kernel::ref_ptr<DATA> >::const_iterator i = _data.find(k);
					if ( i != _data.end() )
						return i->second.get();
				}

				{
					FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
					typename std::map<KEY,FD::Kernel::ref_ptr<DATA> >::iterator i = _data.find(k);
					if ( i != _data.end() )
						return i->second.get();

					_data[k] = newDataIfNeeded;
					return newDataIfNeeded;
				}
			}

			void remove(KEY k)
			{
				FD::Kernel::ScopedLock<FD::Kernel::Mutex> exclusive(_mutex);
				_data.erase( k );
			}

			void remove(DATA* data)
			{
				FD::Kernel::ScopedLock<FD::Kernel::Mutex> exclusive(_mutex);
				for( typename std::map<KEY,FD::Kernel::ref_ptr<DATA> >::iterator i = _data.begin(); i != _data.end(); ++i )
				{
					if ( i->second.get() == data )
					{
						_data.erase( i );
						break;
					}
				}
			}

		private:
			std::map<KEY,FD::Kernel::ref_ptr<DATA> >    _data;
			FD::Kernel::Mutex  _mutex;
		};

		/** Template for thread safe per-object data storage */
		template<typename KEY, typename DATA>
		struct PerObjectObsMap
		{
			DATA* get(KEY k)
			{
				FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
				typename std::map<KEY, FD::Kernel::observer_ptr<DATA> >::const_iterator i = _data.find(k);
				if ( i != _data.end() )
					return i->second.get();

				return 0L;
			}

			DATA* getOrCreate(KEY k, DATA* newDataIfNeeded)
			{
				FD::Kernel::ref_ptr<DATA> _refReleaser = newDataIfNeeded;
				{
					FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
					typename std::map<KEY,FD::Kernel::observer_ptr<DATA> >::const_iterator i = _data.find(k);
					if ( i != _data.end() )
						return i->second.get();
				}

				{
					FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
					typename std::map<KEY,FD::Kernel::observer_ptr<DATA> >::iterator i = _data.find(k);
					if ( i != _data.end() )
						return i->second.get();

					_data[k] = newDataIfNeeded;
					return newDataIfNeeded;
				}
			}

			void remove(KEY k)
			{
				FD::Kernel::ScopedLock<FD::Kernel::Mutex> exclusive(_mutex);
				_data.erase( k );
			}

			void remove(DATA* data)
			{
				FD::Kernel::ScopedLock<FD::Kernel::Mutex> exclusive(_mutex);
				for( typename std::map<KEY,FD::Kernel::observer_ptr<DATA> >::iterator i = _data.begin(); i != _data.end(); ++i )
				{
					if ( i->second.get() == data )
					{
						_data.erase( i );
						break;
					}
				}
			}

		private:
			std::map<KEY,FD::Kernel::observer_ptr<DATA> >    _data;
			FD::Kernel::Mutex       _mutex;
		};


		/** Template for thread safe observer set */
		template<typename T>
		struct ThreadSafeObserverSet
		{
			typedef void (*Functor)(T*);
			typedef void (*ConstFunctor)(const T*);

			void iterate( const Functor& f )
			{
				FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
				for( typename std::set<T>::iterator i = _data.begin(); i != _data.end(); )
				{
					if ( i->valid() )
					{
						f( i->get() );
						++i;
					}
					else
					{
						i = _data.erase( i );
					}
				}
			}

			void iterate( const ConstFunctor& f )
			{
				FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
				for( typename std::set<T>::iterator i = _data.begin(); i != _data.end(); )
				{
					if ( i->valid() )
					{
						f( i->get() );
						++i;
					}
					else
					{
						i = _data.erase( i );
					}
				}
			}

			void insert(T* obj)
			{
				FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
				_data.insert( obj );
			}

			void remove(T* obj)
			{
				FD::Kernel::ScopedLock<FD::Kernel::Mutex> lock(_mutex);
				_data.erase( obj );
			}

		private:
			std::set<FD::Kernel::observer_ptr<T> >      _data;
			FD::Kernel::Mutex  _mutex;
		};
	}
}
#endif // OSGEARTH_CONTAINERS_H
